﻿using System;
using System.Collections.Generic;

namespace SortingAndMerging
{
    public class Sorter
    {
        public static List<int> QuickSort(List<int> arr)
        {
            if (arr.Count <= 1)
            {
                return arr;
            }
            int pivot = arr[arr.Count / 2];
            var left = new List<int>();
            var middle = new List<int>();
            var right = new List<int>();

            foreach (int x in arr)
            {
                if (x < pivot)
                {
                    left.Add(x);
                }
                else if (x > pivot)
                {
                    right.Add(x);
                }
                else
                {
                    middle.Add(x);
                }
            }
            return QuickSort(left).Concat(middle).Concat(QuickSort(right)).ToList();
        }

        public static List<int> MergeSortedArrays(List<int> arr1, List<int> arr2)
        {
            var merged = new List<int>();
            int i = 0, j = 0;

            while (i < arr1.Count && j < arr2.Count)
            {
                if (arr1[i] < arr2[j])
                {
                    merged.Add(arr1[i++]);
                }
                else
                {
                    merged.Add(arr2[j++]);
                }
            }

            while (i < arr1.Count)
            {
                merged.Add(arr1[i++]);
            }

            while (j < arr2.Count)
            {
                merged.Add(arr2[j++]);
            }

            return merged;
        }
    }
}